package org.liaohailong.helloworld.stack;

import java.util.LinkedList;
import java.util.List;

/**
 * Author: liaohailong
 * Time: 2021/5/19 17:14
 * Describe:
 */
public class Conclusion {

    // LC 合并两个有序链表 - 非递归
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        ListNode head = null;
//        ListNode node = null;
//        ListNode node1 = l1;
//        ListNode node2 = l2;
//        while (true) {
//            if (node1 == null && node2 == null) {
//                break;
//            } else if (node1 != null && node2 == null) {
//                if (head == null) {
//                    head = node1;
//                    node = head;
//                } else {
//                    node.next = node1;
//                    node = node.next;
//                }
//                node1 = node1.next;
//            } else if (node1 == null && node2 != null) {
//                if (head == null) {
//                    head = node2;
//                    node = head;
//                } else {
//                    node.next = node2;
//                    node = node.next;
//                }
//                node2 = node2.next;
//            } else if (node1.val < node2.val) {
//                if (head == null) {
//                    head = node1;
//                    node = head;
//                } else {
//                    node.next = node1;
//                    node = node.next;
//                }
//                node1 = node1.next;
//            } else {
//                if (head == null) {
//                    head = node2;
//                    node = head;
//                } else {
//                    node.next = node2;
//                    node = node.next;
//                }
//                node2 = node2.next;
//            }
//        }
//
//        return head;
//    }


    // LC 合并两个有序链表 - 递归
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        ListNode prev = new ListNode(-1);
//        mergeTwoLists(prev, l1, l2);
//        return prev.next;
//    }
//
//    public void mergeTwoLists(ListNode prev, ListNode l1, ListNode l2) {
//        if (l1 == null && l2 == null) return;
//        if (l1 != null && l2 != null) {
//            if (l1.val < l2.val) {
//                prev.next = l1;
//                l1 = l1.next;
//            } else {
//                prev.next = l2;
//                l2 = l2.next;
//            }
//            prev = prev.next;
//        } else if (l1 != null && l2 == null) {
//            prev.next = l1;
//            l1 = l1.next;
//            prev = prev.next;
//        } else if (l1 == null && l2 != null) {
//            prev.next = l2;
//            l2 = l2.next;
//            prev = prev.next;
//        }
//        mergeTwoLists(prev, l1, l2);
//    }

    // LC 合并两个有序链表 - 递归 - 教科书版
    // 时间复杂度O(n + m) 空间复杂度O(n + m)
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        if (l1 == null) {
//            return l2;
//        }
//        else if (l2 == null) {
//            return l1;
//        }
//        else if (l1.val < l2.val) {
//            l1.next = mergeTwoLists(l1.next, l2);
//            return l1;
//        }
//        else {
//            l2.next = mergeTwoLists(l1, l2.next);
//            return l2;
//        }
//    }

    // LC 合并两个有序链表 - 非递归 - 教科书版
    // 时间复杂度O(n + m) 空间复杂度O(1)
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // maintain an unchanging reference to node ahead of the return node.
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // exactly one of l1 and l2 can be non-null at this point, so connect
        // the non-null list to the end of the merged list.
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }


    // LC 第K个语法符号
//    public int kthGrammar(int n, int k) {
//        return getUpNum(k - 1);
//    }
//
//    int getUpNum(int k) {
//        if (k == 0) return 0;
//        int a = getUpNum(k / 2);
//        if (k % 2 == 0) return a;
//        else return 1 - a;
//    }

    // LC 第K个语法符号 - 递归 - 教科书版
//    public int kthGrammar(int N, int K) {
//        if (N == 1) return 0;
//        return (~K & 1) ^ kthGrammar(N - 1, (K + 1) / 2);
//    }

    // LC 第K个语法符号 - 二进制计数法 - 教科书版
//    public int kthGrammar(int N, int K) {
//        return Integer.bitCount(K - 1) % 2;
//    }

    // LC 第K个语法符号
    // n 表示层数，从1开始
    // k 表示列数，从1开始
    public int kthGrammar(int n, int k) {
        int[] record = new int[]{0};
        int val = _kthGrammar(n, k - 1, record);
        if (record[0] % 2 == 1) val = 1 ^ val;
        return val;
    }

    private int _kthGrammar(int n, int k, int[] record) {
        if (k > 2) {
            int cnt = 1 << (n - 1);
            int half = cnt >> 1;
            // k值可能在half以内，不需要对折
            if (k >= half) {
                k %= half;
                record[0]++;
            }
            n--;
            return _kthGrammar(n, k, record);
        } else {
            if (k == 2) record[0]++;
            return k % 2;
        }
    }


    // 不同的二叉搜索树 II
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<>();
        }
        return _generateTrees(1, n);
    }

    private List<TreeNode> _generateTrees(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = _generateTrees(start, i - 1);
            List<TreeNode> rightTrees = _generateTrees(i + 1, end);

            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = leftTree;
                    treeNode.right = rightTree;
                    allTrees.add(treeNode);
                }
            }
        }

        return allTrees;
    }


    public static final class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
